There are many environments in which data needs to be transferred from a source to a destination at high speed with accuracy. For example, computer networks are one such environment. A network topology generally consists of a number of network devices, such as personal computer, routers, switches, etc. interconnected via a carrier such as a twisted-pair cable, fiber optic cable, T1 or T3 line, or the like. Technological advances are continually increasing the bandwidth capabilities of carriers. While in 1980 the maximum bandwidth of carriers was only 2400 bits per second, today optical carriers are capable of supporting a range of 1 to 13 Gigabits per second. The exponential advance in carrier capability has put a burden on the manufacturers of network devices to provide components that are capable of utilizing the available bandwidth.
Typical network devices include a line card that interfaces to the carrier for controlling the transmission of data between the network device and the carrier. Some data is processed by the receiving network device, while other data is merely transferred through the network device. Queuing mechanisms are generally included in the line card for storing received data while it is determined how the data should be processed. It is important that data which is received from the carrier at the high speed line rate is handled appropriately by the receiving device. For example, queues may be assigned to different types of traffic that is destined for the network device to allow the device to process higher priority data first.
Various methods have been developed for cycling through the queues to obtain packets for processing by the network device. For example, queues may be selected by the use of a round robin selection criteria or priority based scheduling. Each of these methods of queue scheduling has their drawbacks. While strict round robin scheduling mechanisms are relatively simple to implement, they may frustrate the servicing of high priority data traffic. Alternatively while priority based scheduling may permit quality of service (QoS) to be maintained, often priority mechanisms increase both the hardware complexity of the selection criteria and the buffering needs for lower priority queues. It would be desirable to determine a method of queue selection that would minimize hardware complexity while assuring quality of service constraints are met for various types of traffic.